package _1091_Shortest_Path_in_Binary_Matrix;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 执行用时：14 ms, 在所有 Java 提交中击败了71.00%的用户
 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了89.44%的用户
 */

public class Solution {

    public int shortestPathBinaryMatrix(int[][] grid) {

        int n = grid.length, m = grid[0].length;
        boolean[][] st = new boolean[n][m];
        int[][] dist = new int[n][m];

        if (grid[0][0] == 1) return -1;

        // BFS
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        st[0][0] = true;
        dist[0][0] = 1;
        while (!q.isEmpty()) {
            int t = q.remove();
            int x = t / m, y = t % m;  // 一维坐标转二维

            for (int a = x - 1; a <= x + 1; a++)
                for (int b = y - 1; b <= y + 1; b++)
                    if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && grid[a][b] == 0) {
                        q.add(a * m + b);
                        st[a][b] = true;
                        dist[a][b] = dist[x][y] + 1;

                        if (a == n - 1 && b == m - 1) return dist[a][b];
                    }
        }

        return -1;
    }

    public static void main(String[] args) {

        int[][] grid = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
        System.out.println((new Solution()).shortestPathBinaryMatrix(grid));
    }
}
